package q2334_validSubarraySize;

import CommonClass.UF;

import java.util.Arrays;
import java.util.stream.IntStream;

public class Solution_1 {
    public static void main(String[] args) {
        int[] arr = {1, 3, 4, 3, 1};
        var ids = IntStream.range(0, arr.length).boxed().toArray(Integer[]::new); // 0 1 2 3 4
        Arrays.sort(ids, (i, j) -> arr[j] - arr[i]); // [2, 1, 3, 0, 4]
        System.out.println(Arrays.toString(ids));
    }
    /*
    此题用并查集理解的难度相对较高
    首先构建一个n + 1的并查集
    用并查集，遍历到 nums[i] 时，用并查集合并 i 和 i+1，这样可以把连续访问过的位置串起来（注意串起来的最后一个元素还没访问过），
    那么 i 所处的连通块的大小减一就是 k
    并且通过对ids的排序 可以保证遍历过程中nums[i]是越来越小的

    前面所遍历过的nums[i*]都是要大于等于当前的nums[i]的
    所以nums[i] > threshold / (uf.getSize(j) - 1)满足条件时 就能够返回答案
     */
    public int validSubarraySize(int[] nums, int threshold) {
        var n = nums.length;
        UF uf = new UF(n + 1);
        // 这一段的作用是构建一个0 -> (n - 1)的下标数组 也就是 0, 1, 2, ... n-1
        var ids = IntStream.range(0, n).boxed().toArray(Integer[]::new);
        // 然后按照在nums中的大小，为下标数组进行排序，其中数字最大的num，其下标排在ids最前面
        Arrays.sort(ids, (i, j) -> nums[j] - nums[i]);
        for (var i : ids) {
            var j = uf.find(i + 1);
            uf.union(i, j);
            if (nums[i] > threshold / (uf.getSize(j) - 1)) return uf.getSize(j) - 1;
        }
        return -1;
    }

}
